#ifndef GRAPH_H
#define GRAPH_H
#include "dist_calculator.h"
#include <vector>
#include <string>
#include "assert.h"

class IGraph
{
public:
    virtual size_t numVertecies() const = 0;
    virtual bool isConnected(size_t u, size_t v) const = 0;
    virtual const std::vector<size_t>& incendents(size_t u) const = 0;
    virtual size_t degree(size_t u) const
    {
        return incendents(u).size();
    }
    virtual size_t vertex(size_t u) const = 0;
    virtual std::string name() const = 0;

};

class FullGraph: public IGraph
{
public:
    FullGraph(size_t minDist, size_t maxDist)
        :minDist_(minDist), maxDist_(maxDist)
    {
        for(size_t u = 0; u < SIZE_VMSK; ++u) {
            for(size_t v = 0; v < SIZE_VMSK; ++v) {
                if (isConnected(u, v)) {
                    incendents_[u].push_back(v);
                }
            }
        }
    }

    bool isConnected(size_t u, size_t v) const
    {
        size_t d = distanceCalculator(u, v);
        return minDist_ <= d && d <= maxDist_;
    }

    const std::vector<size_t>& incendents(size_t u) const
    {
        return incendents_[u];
    }

    size_t numVertecies() const
    {
        return SIZE_VMSK;
    }

    size_t vertex(size_t u) const
    {
        return u;
    }

    std::string name() const
    {
        char res[100];
        sprintf(res, "full_graph_%d_%d", (int)minDist_, (int)maxDist_);
        return res;                                          
    }

private:
    size_t minDist_, maxDist_;
    std::vector<size_t> incendents_[SIZE_VMSK];
};

class FullEvenGraph: public IGraph
{
public:
    FullEvenGraph(size_t minDist, size_t maxDist)
        :minDist_(minDist), maxDist_(maxDist)
    {
        for(size_t u = 0; u < SIZE_VMSK; ++u) {
            for(size_t v = 0; v < SIZE_VMSK; ++v) {
                if (isConnected(u, v)) {
                    incendents_[u].push_back(v);
                }
            }
        }
    }

    bool isConnected(size_t u, size_t v) const
    {
        size_t d = distanceCalculator(u, v);
        return minDist_ <= d && d <= maxDist_
            && ((distanceCalculator(u, 0) & 1) == 0)
            && ((distanceCalculator(v, 0) & 1) == 0);
    }

    const std::vector<size_t>& incendents(size_t u) const
    {
        return incendents_[u];
    }

    size_t numVertecies() const
    {
        return SIZE_VMSK;
    }

    size_t vertex(size_t u) const
    {
        return u;
    }

    std::string name() const
    {
        char res[100];
        sprintf(res, "full_even_graph_%d_%d", (int)minDist_, (int)maxDist_);
        return res;                                          
    }

private:
    size_t minDist_, maxDist_;
    std::vector<size_t> incendents_[SIZE_VMSK];
};

class Graph: public IGraph
{
public:
    Graph(size_t minDist, size_t maxDist, const std::vector<size_t>& vertecies)
        :minDist_(minDist), maxDist_(maxDist), vertecies_(vertecies)
    {
        for(size_t u = 0; u < vertecies.size(); ++u) {
            for(size_t v = 0; v < vertecies.size(); ++v) {
                if (isConnected(u, v)) {
                    incendents_[u].push_back(v);
                }
            }
        }
    }

    bool isConnected(size_t u, size_t v) const
    {
        size_t d = distanceCalculator(vertecies_[u], vertecies_[v]);
        return minDist_ <= d && d <= maxDist_;
    }

    const std::vector<size_t>& incendents(size_t u) const
    {
        return incendents_[u];
    }

    size_t numVertecies() const
    {
        return vertecies_.size();
    }

    size_t vertex(size_t u) const
    {
        return vertecies_[u];
    }

    std::string name() const
    {
        char res[100];
        sprintf(res, "graph_%d_%d", (int)minDist_, (int)maxDist_);
        return res;                                          
    }

private:
    size_t minDist_, maxDist_;
    std::vector<size_t> vertecies_;
    std::vector<size_t> incendents_[SIZE_VMSK];
};

class SubGraph: public IGraph
{
public:
    SubGraph(const IGraph* const graph, const std::vector<size_t>& vertecies)
        :graph_(graph), vertecies_(vertecies)
    {
        for(size_t u = 0; u < vertecies.size(); ++u) {
            for(size_t v = 0; v < vertecies.size(); ++v) {
                if (isConnected(u, v)) {
                    incendents_[u].push_back(v);
                }
            }
        }
    }

    bool isConnected(size_t u, size_t v) const
    {
        return graph_->isConnected(vertecies_[u], vertecies_[v]);
    }

    const std::vector<size_t>& incendents(size_t u) const
    {
        return incendents_[u];
    }

    size_t numVertecies() const
    {
        return vertecies_.size();
    }

    size_t vertex(size_t u) const
    {
        return graph_->vertex(vertecies_[u]);
    }

    std::string name() const
    {
        return "sub_graph_of_" + graph_->name();
    }

private:
    const IGraph* const graph_;
    std::vector<size_t> vertecies_;
    std::vector<size_t> incendents_[SIZE_VMSK];

};

class CommonGraph: public IGraph
{
public:
    CommonGraph(size_t numVertecies)
        :numVertecies_(numVertecies)
    {
    }

    bool isConnected(size_t u, size_t v) const
    {
        return std::find(incendents_[u].begin(), incendents_[u].end(), v)
            != incendents_[u].end();
    }

    const std::vector<size_t>& incendents(size_t u) const
    {
        return incendents_[u];
    }

    size_t numVertecies() const
    {
        return numVertecies_;
    }

    size_t vertex(size_t u) const
    {
        return u;
    }

    void addEdge(size_t u, size_t v)
    {
        assert(u < numVertecies_);
        assert(v < numVertecies_);
        incendents_[u].push_back(v);
        incendents_[v].push_back(u);
    }

    std::string name() const
    {
        char res[100];
        sprintf(res, "common_graph_%zu", numVertecies_);
        return res;
    }

private:
    size_t numVertecies_;
    std::vector<size_t> incendents_[SIZE_VMSK];

};

size_t naiveColoring(const IGraph* const graph);
size_t runningNaiveColoring(const IGraph* const graph);

bool correctColoring(const IGraph* const graph);

bool biparate(const IGraph* const graph);

void draw(const IGraph* const graph, std::ostream& out);
void draw(const IGraph* const graph, std::string fname);


#endif//GRAPH_H
